COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00009 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A01.Tex(AOO,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, March 10, 1989}
\leftline{\sevenrm Unpublished draft}

\noindent MAXD2

Let $A[1: N, 1: M]$ be an array of real numbers.  Find the rectangular
subarray over which the sum is largest.  That is, we want to maximize
$${\rm Sum} (r↓1, r↓2, c↓1, c↓2) = \sum↓{\scriptstyle r↓1 < i \leq r↓2\atop
\scriptstyle c↓1 < j \leq c↓2}A↓{ij}$$
subject to $0\leq r↓1 < r↓2 \leq N$, $0\leq c↓1 < c↓2\leq M$.  Define
$$S↓{p,q} = \sum↓{\scriptstyle 0 < i \leq p\atop\scriptstyle 0 < j 
\leq q}A↓{ij}.$$  Then
${\rm Sum} (r↓1, r↓2, c↓1, c↓2) = (S↓{r↓2c↓2} - S↓{r↓1c↓2}) - (S↓{r↓2c↓1} 
- S↓{r↓1c↓1})$.  In particular, 
$$A↓{r↓2c↓2} = {\rm Sum} (r↓2-1, {r↓2, c↓2-1, c↓2}) = (S↓{r↓2c↓2} - 
S↓{r↓2-1, c↓2})- (S↓{r↓2, c↓2-1}- S↓{r↓2-1, c↓2-1})$$
can be used to compute $S$ from $A$ efficiently.  
The algorithm to maximize the sum first computes all $S↓{rc}$.  The value of
$A↓{rc}$ is last used in computing $S↓{rc}$, so the two arrays could share
the same storage space.  
In the second stage, the algorithm iterates over all eligible $r↓1$, $r↓2$, and 
$c↓2$.  For each such triple, it maximizes Sum by minimizing $S↓{r↓2c↓1} - 
S↓{r↓1c↓1}$ for values of $c↓1$ less than $c↓2$.  This minimum can be simply
updated whenever $c↓2$ changes, so it does not require a fourth level of
iteration.  The algorithm follows.

{\obeylines
{\bf FOR} $r:=0$ {\bf TO} $n$ {\bf DO} $S↓{r,0} ← 0$; {\bf FOR} $c:=1$ {\bf TO} $m$ {\bf DO} $S↓{0,c} ← 0$; 
{\bf FOR} $r:=1$ {\bf TO} $n$ {\bf DO} {\bf FOR} $c:=1$ {\bf TO} $m$ {\bf DO}
\quad $S↓{r,c} ← A↓{r,c} + S↓{r-1,c} + S↓{r,c-1} - S↓{r-1, c-1}$;
${\it MAX} ← - ∞$; ${\it MAXC1, MAXC2, MAXR1, MAXR2} ← 0$;
{\bf FOR} $r2: = 1$ {\bf TO} $n$ {\bf DO} {\bf FOR} $r1: = 0$ {\bf TO} $r2-1$ {\bf DO}
\quad {\bf BEGIN}
\quad {\it MIN} $← 0$; $c1 ← 0$;
\quad {\bf FOR} $c2: = 1$ {\bf TO} $m$ {\bf DO}
\quad\quad {\bf BEGIN}
\quad\quad $D ← S↓{r↓2,c↓2} - S↓{r↓1,c↓2}$;
\quad\quad {\bf IF} $D <$ {\it MIN} {\bf THEN}
\quad\quad {\bf BEGIN} {\it MIN} $← D$; $c↓1 ← c↓2$ {\bf END}
\quad\quad {\bf IF} $D -${\it MIN} $>$ {\it MAX} {\bf THEN}
\quad\qquad {\bf BEGIN} {\it MAX} $← D -$ {\it MIN}; {\it MAXC1} $← c1$; 
\quad\qquad{\it MAXC2} $← c2$; {\it MAXR1} $← r1$; {\it MAXR2} $← r2$ {\bf END}
\quad\quad {\bf END}
\quad {\bf END;}
{\it WRITE (MAX, MAXC1, MAXC2, MAXR1, MAXR2)}\par}

The two innermost loops are executed $NM$ times and ${N(N-1)M}\over 2$ times,
totaling ${N(N+1)M}\over 2$.

I do not believe there is any way to solve this problem in $O(NM)$ time.
Notice that $A↓{rc}$ can be computed in three subtractions from the array $S$, so
any fast algorithm can, within a constant factor, work just as fast using only
the data in $S$.  One readily shows that any set of values may occur in 
$S[1:N$, $1:M]$, so there is no special structure in $S$ to
benefit from.  In effect, the problem has been reformulated as one of maximizing
$(S↓{r↓2c↓2} - S↓{r↓1c↓2}) - (S↓{r↓2c↓1} - S↓{r↓1c↓1})$.  
Suppose a little bird had told us that {\rm BIG} is in fact the maximum value of that
formula and all we had to do is find the rectangle that achieves it.  We would
be trying to achieve
$$S↓{r↓2c↓2} - S↓{r↓1c↓2} - S↓{r↓2c↓1} + S↓{r↓1c↓1} \geq {\rm BIG}.$$
This inequality can be rearranged variously, but however it is rearranged, one side
of the inequality will contain at least three of the subscripts and will have
to be evaluated $O(N↑2M)$ or $O(MN↑2)$ times.  One can't locate the rectangle
without testing something equivalent to the inequality.  Hardly a proof, but it 
discourages me.
\bye